#include "big_int.h"

big_int::big_int() : shift(0), versa(false)
{
	a_nums.push(0);
}
big_int::big_int(long long num) : shift(0), versa(num < 0)
{
	a_nums.push(std::abs(num));
}
big_int::big_int(const big_int& bigint) : shift(bigint.shift), versa(bigint.versa)
{
	a_nums = bigint.a_nums;
}
big_int::big_int(const std::string& str) : shift(0), versa(false)
{   
	int begin = 0;
	versa = (str[0] == '-');
	if (str[0] == '-' || str[0] == '+')
	{
		begin = 1;
	}
	unsigned int counter = 0;
	long long temp = 0;
	a_nums.clear();
	int len = str.length();
	for (int i = len - 1; i >= begin; i--)
	{
		if (counter == big_int::digits)
		{
			a_nums.push(temp);
			temp = 0;
			counter = 0;
		}
		int d = (str[i] - '0');
		for (unsigned int i = 0; i < counter; i++)
		{
			d *= 10;
		}
		temp += d;
		counter++;
	}
	a_nums.push(temp);
	if (a_nums.size() == 0)
	{
		a_nums.push(0);
	}
	crop();
}
big_int& big_int::operator=(const big_int& bigint)
{
	if (this == &bigint)
	{
		return *this;
	}
	versa = bigint.versa;
	shift = bigint.shift;
	a_nums = bigint.a_nums;
	return *this;
}
void big_int::swap(big_int& bigint)
{
	std::swap(shift, bigint.shift);
	std::swap(versa, bigint.versa);
	a_nums.swap(bigint.a_nums);
}
big_int big_int::abs() const
{
	return (versa ? -*this : *this);
}
int big_int::comp(const big_int& bigint) const
{
	if (versa && !bigint.versa)
	{
		return -1;
	}
	if (!versa && bigint.versa)
	{
		return 1;
	}
	if (versa && bigint.versa)
	{
		return -(abs().comp(bigint.abs()));
	}
	if (a_nums.size() + shift != bigint.a_nums.size() + bigint.shift)
	{
		if (a_nums.size() + shift < bigint.a_nums.size() + bigint.shift)
		{
			return -1;
		}
		else
		{
			return 1;
		}
	}
	int len = a_nums.size();
	for (int i = len - 1; i >= 0; i--)
	{
		int j = i - bigint.shift + shift;
		long long d = (0 <= j && j < static_cast<int>(bigint.a_nums.size())) ? bigint.a_nums[j] : 0;
		if (a_nums[i] < d) {
			return -1;
		}
		if (a_nums[i] > d) {
			return 1;
		}
	}
	return 0;
}
bool big_int::operator<(const big_int& bigint) const
{
	return comp(bigint) < 0;
}
bool big_int::operator>(const big_int& bigint) const
{
	return comp(bigint) > 0;
}
bool big_int::operator<=(const big_int& bigint) const
{
	return comp(bigint) <= 0;
}
bool big_int::operator>=(const big_int& bigint) const
{
	return comp(bigint) >= 0;
}
bool big_int::operator==(const big_int& bigint) const
{
	return comp(bigint) == 0;
}
bool big_int::operator!=(const big_int& bigint) const
{
	return comp(bigint) != 0;
}
big_int& big_int::operator+=(const big_int& bigint)
{
	if (bigint == big_int(0))
	{
		return *this;
	}
	if (!versa && bigint.versa)
	{
		return *this -= bigint.abs();
	}
	if (versa && !bigint.versa)
	{
		big_int temp = (*this).abs();
		*this = bigint;
		return *this -= temp;
	}
	if (versa && bigint.versa)
	{
		*this = (*this).abs();
		*this += bigint.abs();
		*this = -(*this);
		return *this;
	}
	if (a_nums.size() + shift < bigint.a_nums.size() + bigint.shift)
	{
		a_nums.resize(bigint.a_nums.size() + bigint.shift - shift, 0);
	}
	if (shift > bigint.shift)
	{
		a_nums.insert(a_nums.begin(), shift - bigint.shift, 0);
		shift = bigint.shift;
	}
	int len = bigint.a_nums.size();
	for (int i = 0; i < len; i++)
	{
		unsigned int k = i - shift + bigint.shift;
		a_nums[k] += bigint.a_nums[i];
	}
	normalize();
	crop();
	return *this;
}
big_int& big_int::operator-=(const big_int& bigint)
{
	if (bigint == big_int(0))
	{
		return *this;
	}
	if (!versa && bigint.versa)
	{
		return *this += bigint.abs();
	}
	if (versa && !bigint.versa)
	{
		*this = -((*this).abs() + bigint);
		return *this;
	}
	if (versa && bigint.versa)
	{
		*this = bigint.abs() - (*this).abs();
		return *this;
	}
	if (bigint > *this)
	{
		*this = -(bigint - *this);
		return *this;
	}
	if (shift > bigint.shift)
	{
		a_nums.insert(a_nums.begin(), shift - bigint.shift, 0);
		shift = bigint.shift;
	}
	int len = bigint.a_nums.size();
	for (int i = 0; i < len; i++)
	{
		unsigned int k = i - shift + bigint.shift;
		a_nums[k] -= bigint.a_nums[i];
	}
	normalize();
	crop();
	return *this;
}
big_int& big_int::operator*=(long long num)
{
	if (num == 0)
	{
		*this = big_int(0);
		return *this;
	}
	int len = a_nums.size();
	for (int i = 0; i < len; i++)
	{
		a_nums[i] *= num;
	}
	normalize();
	return *this;
}
big_int& big_int::operator*=(const big_int& bigint)
{
	if (bigint == big_int(0))
	{
		*this = big_int(0);
		return *this;
	}
	big_int temp;
	int len = bigint.a_nums.size();
	for (int i = len - 1; i >= 0; i--)
	{
		temp *= base;
		temp += (*this) * bigint.a_nums[i];
	}
	temp.versa = (temp != big_int(0)) && (versa != bigint.versa);
	*this = temp;
	return *this;
}
big_int& big_int::operator/=(const big_int& bigint)
{
	*this = div_and_rem(bigint).first;
	return *this;
}
big_int& big_int::operator%=(const big_int& bigint)
{
	*this = div_and_rem(bigint).second;
	return *this;
}
big_int big_int::operator+(const big_int& bigint) const
{
	big_int temp = *this;
	temp += bigint;
	return temp;
}
big_int big_int::operator-(const big_int& bigint) const
{
	big_int temp = *this;
	temp -= bigint;
	return temp;
}
big_int big_int::operator*(const big_int& bigint) const
{
	big_int temp = *this;
	temp *= bigint;
	return temp;
}
big_int big_int::operator/(const big_int& bigint) const
{
	big_int temp = *this;
	temp /= bigint;
	return temp;
}
big_int big_int::operator%(const big_int& bigint) const
{
	big_int temp = *this;
	temp %= bigint;
	return temp;
}
big_int big_int::operator*(long long num) const
{
	big_int temp = *this;
	temp *= num;
	return temp;
}
big_int big_int::operator-() const
{   
	big_int temp = *this;
	temp.versa = (temp != big_int(0)) && !temp.versa;
	return temp;
}
std::pair<big_int, big_int> big_int::div_and_rem(const big_int& bigint) const
{
	big_int a = (*this).abs();
	big_int b = bigint.abs();
	big_int result;
	int offset = a.a_nums.size() - b.a_nums.size();
	b <<= offset;
	while (a >= bigint.abs())
	{
		long long k = a.quick_div(b);
		result <<= 1;
		result += big_int(k);
		a -= b * k;
		b >>= 1;
		offset--;
	}
	if (offset + 1 > 0)
	{
		result <<= offset + 1;
	}
	result.crop();
	result.versa = (result != big_int(0)) && (versa != bigint.versa);
	a.versa = (a != big_int(0)) && versa;
	return std::make_pair(result, a);
}
big_int& big_int::operator<<=(int offset)
{
	shift += offset;
	return *this;
}
big_int& big_int::operator>>=(int offset)
{
	shift -= offset;
	return *this;
}
big_int big_int::operator<<(int offset) const
{
	big_int temp = *this;
	temp <<= offset;
	return temp;
}
big_int big_int::operator>>(int offset) const
{
	big_int temp = *this;
	temp >>= offset;
	return temp;
}
std::istream& operator>>(std::istream &in, big_int &bigint)
{
	while (std::isspace(in.peek()))
	{
		in.get();
	}
	std::ostringstream ss;
	if (in.peek() == '-' || in.peek() == '+')
	{
		char sign;
		in.get(sign);
		ss << sign;
	}
	if (!isdigit(in.peek())) {
		in.setstate(std::ios_base::badbit);
		return in;
	}
	while (isdigit(in.peek()))
	{
		char temp;
		in.get(temp);
		ss << temp;
	}
	bigint = big_int(ss.str());
	return in;
}
std::ostream& operator<<(std::ostream &output, const big_int &bigint)
{
	if (bigint.versa)
	{
		output << "-";
	}
	int size = bigint.a_nums.size();
	for (int i = size - 1; i >= 0; i--)
	{
		std::ostringstream out;
		out << bigint.a_nums[i];
		std::string str = out.str();
		if (i != size - 1)
		{
			int count = big_int::digits - str.length();
			for (int i = 0; i < count; i++)
			{
				output << "0";
			}
		}
		output << str;
	}
	std::string zero(bigint.digits, '0');
	for (int i = 0; i < bigint.shift; i++)
	{
		output << zero;
	}
	return output;
}
void big_int::normalize()
{
	long long carry;
	int size = a_nums.size();
	for (int i = 0; i < size - 1; i++)
	{
		if (a_nums[i] >= base)
		{
			carry = a_nums[i] / base;
			a_nums[i] -= carry * base;
			a_nums[i + 1] += carry;
		}
		if (a_nums[i] < 0)
		{
			carry = std::abs((a_nums[i] - base + 1) / base);
			a_nums[i] += carry * base;
			a_nums[i + 1] -= carry;
		}
	}
	carry = 0;
	while (true)
	{
		unsigned int last = a_nums.size() - 1;
		if (a_nums[last] < 0)
		{
			carry = -std::abs((a_nums[last] - base + 1) / base);
			a_nums[last] -= carry * base;
		}
		if (a_nums[last] >= base)
		{
			carry = a_nums[last] / base;
			a_nums[last] -= carry * base;
		}
		if (carry == 0)
		{
			break;
		}
		else if (carry == -1)
		{
			*this = -((big_int(1) << a_nums.size()) - *this);
			break;
		}
		else
		{
			a_nums.push(carry);
			carry = 0;
		}
	}
}
long long big_int::quick_div(const big_int& bigint) const
{
	long long l = 0;
	long long r = base;
	long long m = (l + r) / 2;
	while (l + 1 != r)
	{
		if (*this < bigint * m)
		{
			r = m;
		}
		else
		{
			l = m;
		}
		m = (l + r) / 2;
	}
	return m;
}
void big_int::crop()
{
	while (a_nums.size() > 1 && a_nums[a_nums.size() - 1] == 0)
	{
		a_nums.pop();
	}
	if (a_nums.size() == 1 && a_nums[0] == 0)
	{
		shift = 0;
	}
}
big_int abs(const big_int& bigint)
{
	return bigint.abs();
}